// var coinChange = function(coins, amount) {
//   const dp = (conis,amount) =>{
//       if(amount===0) return 0
//       if(amount<0) return -1
//       let res = Number.MAX_SAFE_INTEGER
//       for(let coin of conis) {
//           let subProblem = dp(conis,amount-coin) 
//           if(subProblem==-1) continue
//           res = Math.min(res,subProblem+1)
//       }
//       return res===Number.MAX_SAFE_INTEGER? -1 : res
//   }
//  return dp(coins,amount)
// };

// 带备忘录的
// function coinChange (coins, amount) {
//   const memo = new Array(amount + 1).fill(-10)
//   const dp = (coins, amount) => {
//     if (amount === 0) return 0
//     if (amount < 0) return -1
//     if (memo[amount] !== -10) return memo[amount]
//     let res = Number.MAX_SAFE_INTEGER
//     for (let coin of coins) {
//       let subProblem = dp(coins, amount - coin)
//       if (subProblem === -1) continue
//       res = Math.min(res, subProblem + 1)
//     }
//     memo[amount] = (res === Number.MAX_SAFE_INTEGER ? -1 : res)
//     return memo[amount]
//   }
//   return dp(coins, amount)
// }

// 迭代法
function coinChange (coins, amount) {
  const dp = new Array(amount + 1).fill(amount + 1)
  dp[0] = 0
  for (let i = 0; i < dp.length; i++) {
    for (let coin of coins) {
      // 无解 则跳过
      if (i - coin < 0) continue
      dp[i] = Math.min(dp[i], 1 + dp[i - coin])
    }
  }
  return (dp[amount] == amount + 1) ? -1 : dp[amount]
}
let coins = [1, 2, 5, 7, 10, 20], amount = 880
console.time('timer')
console.log(coinChange(coins, amount))
console.timeEnd('timer')

